/**
 * Mario Roberto Gómez Flores (12165)
 * Pablo Estrada (12121)
 * Miguel Novella (12164)
 * Alberto Suriano (12281) * 
 *
 */

public class Sorter {
    
    public void insertion(Comparable[] lista){
        //lista = lista.toArray; //vuelve array 
	int largo = lista.length; //cantidad de elementos a ordenar
        int numOrdenados = 1; //cantidad de numeros ordenados
	int i;
		
        while(numOrdenados < largo){ //mientras no se haya ordenado todo elemento...
           
            Comparable temp1 = lista[numOrdenados];		
            for(i = numOrdenados; i > 0; i--){ //revisa en reversa e intercambia
               
                if(temp1.compareTo(lista[i-1]) < 0){ //si es menor que el elemento
                    lista[i] = lista[i-1];
                }
		else{
                    break;
		}
            }
            lista[i] = temp1;//reinserta elemento
            numOrdenados++;//incrementa contador
        }	
    }

    //Ordena un array usando bubbleSort
    public void bubble(Comparable[] lista){
        //Obtener el largo de la lista
        int n = lista.length;

        //Bandera que indica si se intercambio algun par de elementos
        boolean swapped;

        //Se entra al ciclo mientras se hayan cambiado elementos
        do{
            //Reiniciar la bandera
            swapped = false;

            //Recorre toda la lista
            for(int i=1; i<n; i++){
                //Si el elemento i-1 es mayor que el i
                if(lista[i-1].compareTo(lista[i]) > 0){
                    //Los intercambia
                    intercambiar(lista, i-1, i);

                    //Cambia la bandera
                    swapped = true;
                }
            }

            //Cuando termina, ya no comparara el ultimo elemento en la proxima, asi que reduce n por 1.
            n--;
        }
        while(swapped);
    }

    //Intercambia la posicion de dos objetos de un arreglo
    private void intercambiar(Object[] arreglo, int x, int y){
        Object temp = arreglo[x];   //Almacenar el primer elemento
        arreglo[x] = arreglo[y];    //Colocar el segundo en el lugar del primero
        arreglo[y] = temp;          //Regresar el primero al lugar del segundo
    }

    //Ordena un array usando quickSort
    public void quick(Comparable[] lista){
        //Llama al metodo de apoyo recursivo
        quickSortRecursivo(lista, 0, lista.length-1);
    }

    //Metodo de apoyo a quick
    private void quickSortRecursivo(Comparable[] lista, int left, int right){
        //Variable que almacenara la localizacion del pivote cuando termine el metodo
        int pivote;

        //Si el puntero izquierdo efectivamente esta a la izquierda
        if(left < right){
            //Coloca el primer pivote en su lugar y obtiene su localizacion
            pivote = ordenarParticion(lista, left, right);

            //Se llama a si mismo para ordenar los objetos de la izquierda del pivote
            quickSortRecursivo(lista, left, pivote-1);

            //Y para ordenar los de la derecha del pivtoe
            quickSortRecursivo(lista, pivote+1, right);
        }
    }

    //Ordena una parte de un array usando quickSort
    private int ordenarParticion(Comparable[] lista, int left, int right){
        while(true){
            //Primera parte: mover el puntero de derecha a izquierda
            while(left < right && lista[left].compareTo(lista[right])<0)
                //Si el puntero sigue a la izquierda y el objeto de la izquierda es menor que el de la derecha
                //Mueve el puntero derecho
                right--;
            //Si sale del ciclo, o left==right o el objeto izquierdo no es menor que el derecho
            if(left < right)
                //Intercambia los objetos
                intercambiar(lista, left++, right);
            //Si left==right, termino el algoritmo
            else
                //Devuelve el indice donde termino el pivtoe
                return left;

            //Segunda parte: mover el puntero de izquierda a derecha
            while(left < right && lista[left].compareTo(lista[right])<0)
                //Si el puntero sigue a la izquierda y el objeto de la izquierda es menor que el de la derecha
                //Mueve el puntero izquierdo
                left++;
            //Si sale del ciclo, o left==right o el objeto izquierdo no es menor que el derecho
            if(left < right)
                //Intercambia los objetos
                intercambiar(lista, left, right--);
            //Si left==right, termino el algoritmo
            else
                //Devuelve el indice donde termino el pivtoe
                return right;
        }
    }

    public Comparable[] mergeSort(Comparable[] numeros){
        
        if(numeros.length==1){
            return numeros;
        }
        else{
            int n = (int) Math.floor(numeros.length/2);
            
            //Subarrays
            Comparable[] sub1 = new Comparable[n];
            Comparable[] sub2 = new Comparable[numeros.length-n];
            
            //Copiando elementos del array original en los subarrays
            for(int i=0;i<numeros.length;i++){
                //Si no se ha llegado a la mitad del array se copia en el primer subarray
                if(i<n){
                    sub1[i]=numeros[i];
                }
                else{
                    sub2[i-n] =numeros[i];
                }
           
            }
            //Divide y venceras: volvemos a dividir los subarrays    
            sub1 = mergeSort(sub1);
            sub2 = mergeSort(sub2);
            numeros = (Comparable[]) merge(sub1,sub2);
            return numeros;        
            
            
        
        }       
    }
    
    private Object[] merge(Comparable[] array1, Comparable[] array2){
        Comparable[] nuevoArray = new Comparable[array1.length+array2.length];
        int i,elementosCopiados1=0,elementosCopiados2=0;
        for(i=0;i<array1.length+array2.length;i++){
            if(elementosCopiados1==array1.length){
                nuevoArray[i] = array2[elementosCopiados2];
                elementosCopiados2++;
            }
            else if(elementosCopiados2==array2.length){
                nuevoArray[i] = array1[elementosCopiados1];
                elementosCopiados1++;
            }
            else if(array1[elementosCopiados1].compareTo(array2[elementosCopiados2])==1){
                nuevoArray[i]=array2[elementosCopiados2];
                elementosCopiados2++;                          
            }
            else{
                nuevoArray[i]=array1[elementosCopiados1];
                elementosCopiados1++;
            }
            
        }
        return nuevoArray;
    }    
}